#include "stand.h"

extern int a[];

void insertSort(int a[],int ac)
{
	int i,j,k,q;
	for (i = 1;i < ac; i++) {
		for (j=0; j<i ;j++) {
			if (a[i] > a[j]) {
				swap(a+i,a+j);
			}
		}
	}
}


int main()
{
	/*
	 * 目标：希尔排序，
	 * 思路：使用d=4,ac=10。int *nsub;
	 * 	使用malloc为nsub申请一段内存大小为4的地址空间。
	 * 	使用nsub[i]=a[i+j*d]   //j是分组的组数
	 * 	排完序后，将数组的值在进行调换。a[i+j*d] = nsub[i];
	 * 	再释放内存
	 * */


	//to operation a
	
	int ac = ARRLEN(a,int);
	print_arr(a,ac);
	int step,i,j,k;
/*
	int step = 4;
	int *nsub;
	int num = 0;

	int i,j,k,l;

	do {
		num ++;
	}while( ac -4*num > 4);
	num ++; 

	printf("%d\n",num);

	nsub = malloc(sizeof(int) *num);

	//目标：取到0，4，8三个元素给nsub
	
	for (j=0;j< step;j++) {
//		num = (ac -i -1)/step + 1;
		
	}

	for (j=0;;j++) {
		//转换数据.
		for (i=0;num*i+j<ac;i++) {
			nsub[i] = a[num*i + j];
		}
		insertSort(nsub,ARRLEN(nsub,int));
		//完成排序后
		for (i=0;num*i+j<ac;i++) {
			a[num*i + j] = nsub[i];
		}
	}

	print_arr(a,ARRLEN(a,int));

	free(nsub);


*/ 
/*

	for (step = ac /2;step > 0;step /=2) {   //step 5 5个元素一组，step/=2， step 5,2，1
	 	//上面的是分组，下面的是将每个分组进行排序。 组分好了，但一个组中包含上面元素，怎么获知？ 组下标，排序时，不要想着只有i++，可以排序，i+=step 也可以当成一个数组，此时i+=step ,就是i++
		for (i=0;i<step;i++) { //使step个分组，都进行排序一次。这里应该循环5次，因为一共分了5个数组
//			for (j=0;j<ac;j=j+step) { //遍历数组中的内容并排序,数组的内容为a[i+step]
			
			for (j =0; j< step;j++) {//五个数组分别进行插入算法。
//				for (k=1;k< ;k++) {
//					
//				}

				if (a[j] > a[j+step]) {
//					swap(a+j,a+(j+step));
				}
//				printf("%d %d %d \n",step,i,j);
			}
		}


	}

	for (step = ac /2; step >0; step /=2) { //步长
		for (i=0; i < step; i++) { //0< 5 ，遍历step个数组

			for (j=i+step; j< ac;j+=step) { //对一个数组
				if (a[j] < a[j-step]) {
				
				}
			}
			
		}
	}


	step = ac /5;
	for  (k=0;k<step;k++) {
		//怎么遍历第一个子数组呢？
		//怎么又使数据遍历完整？
		//变化量是，i+=step, 比较条件是,a[i],a[i-step],a=step;
		for(i=step;i<ac;i+=step) { //这样等于说，取到第一个数组中开头的两个元素。插入算法，将是将第二个数与第一个数，进行比较。再将第三个数与前两个数进行比较。最简单的方式还是，将得到的数据全部放到另外一个临时数组中。
			for (j=0;j<i;j=step*i) {  //j,j+step,j+2*step。。。。
				if (a[i] > a[j]) {
				}
			}
			
		}




		
	}
*/


	i=0;j=0;step=0;

	for (step = ac /2; step > 0; step/=2) { //步长==子数组的个数
		for (i=0; i< step;i++) { //循环每个子数组
			for (j =i+step;j<ac;j+= step) {
				if (a[j] < a [j-step]) { //比较，每个子数组中第一个步长元素与第一个元素。
					int temp = a[j];
					int k = j-step; //得到两个值,一个为临时变量，一个为下标

					while (k>=0 && a[k] > a[j]) { 
						a[k+step] = a[k];
						k -= step;
					}
					a[k+step] = temp;
				}
			}
		}
	
	}



	print_arr(a,ac);




}


/*
 * 使用更多的for，while循环，来降低循环次数。
 * */



/*
 * 1. 将一个数组分成若干子数组
 * 2. 将每个子数组进行一次插入排序。
	 * 插入排序，第一次，0,5，第二次，1,4
 *
 *
 * */















